package 双指针技巧与相关题目;

import java.util.Arrays;

// 救生艇
// 给定数组 people
// people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit
// 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit
// 返回 承载所有人所需的最小船数
// 测试链接 : https://leetcode.cn/problems/boats-to-save-people/

public class Code04_BoatsToSavePeople {

    // 时间复杂度O(n * logn)，因为有排序，额外空间复杂度O(1)
    public static int numRescueBoats(int[] people, int limit) {
        // 让体重数组进行排序
        Arrays.sort(people);
        int l = 0;
        int r = people.length - 1;
        int ans = 0;
        int sum = 0;
        while (l <= r){
            sum = l == r ? people[l] : people[l] + people[r];
            // 最小未被使用的体重 + 最大未被使用的体重 > limit ，则r 位置体重的人单独一船
            if(sum > limit){
                r--;
            }else {
                // 两人一船
                l++;
                r--;
            }
            // 使用船数+1
            ans++;
        }
        return ans;
    }
}
